/**
 * https://leetcode.cn/problems/magnetic-force-between-two-balls/submissions/566028310/
 * 1552. 两球之间的磁力
 * medium 陈贝纯 2024.09.19
 * 二分搜索
 */

class Solution {
public:
    bool check(int mid,vector<int>& position,int m){
        int last=0;
        for(int i=1;i<position.size();++i){
            if(position[i]-position[last]>=mid){
                last=i;
                m--;
            }
        }
        return m<=0;
    }
    int maxDistance(vector<int>& position, int m) {
        sort(position.begin(),position.end());
        int l=0;
        int n=position.size();
        int r=position[n-1];
        int ans=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(check(mid,position,m-1)){
                ans=mid;
                l=mid+1;
            }
            else
            r=mid-1;
        }
        return ans;
    }
};